UVa/10069 - Distinct subsequences/10069.cpp

   1 #include <iostream>
   2
   3 using namespace std;
   4
   5
   6 const int MAX = 200;
   7
   8 class HugeInt {
   9 public:
  10
  11         // vars
  12         char number[MAX];
  13         int length;
  14
  15         // constructors
  16         HugeInt() {
  17                 memset(number,0,sizeof(number));
  18                 length = 1;
  19         }
  20
  21         HugeInt(int n) {
  22                 *this = n;
  23         }
  24
  25         // operators
  26         // takes 'r' as right number and writes result to 'this'
  27         // *veryfied*
  28         HugeInt* operator= (const HugeInt* r) {
  29                 memset(number,0,sizeof(number));
  30                 strcpy(number,r->number);
  31                 length = r->length;
  32                 return this;
  33         }
  34
  35         // *veryfied*
  36         HugeInt* operator= (const int r) {
  37                 memset(number,0,sizeof(number));
  38                 sprintf(number,"%d",r);
  39                 length = strlen(number);
  40                 for (int i = 0; i < (length >> 1); i++) {
  41                         char c = number[i];
  42                         number[i] = number[length-i-1];
  43                         number[length-i-1] = c;
  44                 }
  45                 for (int j = 0; j < length; j++)
  46                         number[j] -= '0';
  47                 return this;
  48         }
  49
  50         // *veryfied*
  51         const HugeInt operator+ (const HugeInt& r) {
  52                 int n = max(length,r.length), carry = 0, k, i;
  53                 HugeInt theNew;
  54                 for (i = 0; i < n || carry; i++) {
  55                         k = number[i] + r.number[i] + carry;
  56                         theNew.number[i] = k % 10;
  57                         carry = k / 10;
  58                 }
  59                 theNew.length = i;
  60                 return theNew;
  61         }
  62
  63         // slightly veryfied
  64         void operator+= (const HugeInt& r) {
  65                 *this = *this + r;
  66         }
  67
  68         // *slightly veryfied*
  69         const HugeInt operator* (const int r) {
  70                 int i, k, carry = 0;
  71                 HugeInt theNew;
  72                 for (i = 0; i < length || carry; i++) {
  73                         k = number[i] * r + carry;
  74                         theNew.number[i] = k % 10;
  75                         carry = k / 10;
  76                 }
  77                 theNew.length = i;
  78                 return theNew;
  79         }
  80
  81         // *slightly veryfied*
  82         void operator*= (const int r) {
  83                 *this = *this * r;
  84                 //return this;
  85         }
  86
  87         // shifts number left by 'shift' positions
  88         // useful when multiplying two HugeInt's
  89         HugeInt operator<< (const int shift) {
  90                 int i;
  91                 HugeInt theNew;
  92                 // don't shift if number is 0 and there is no number
  93                 //if (length == 0 || length == 1 && number[0] == 0) return;
  94                 for (i = length - 1; i >= 0; i--)
  95                         theNew.number[i + shift] = number[i];
  96                 for (i = 0; i < shift; i++)
  97                         theNew.number[i] = 0;
  98                 theNew.length = length + shift;
  99                 return theNew;
 100         }
 101
 102         HugeInt operator* (HugeInt& r) {
 103                 int i;
 104                 HugeInt theNew = 0;
 105                 for (i = 0; i < length; i++)
 106                         theNew += (r << i) * number[i];
 107                 truncate(theNew);
 108                 return theNew;
 109         }
 110
 111         HugeInt operator*= (HugeInt& r) {
 112                 *this = *this * r;
 113                 return *this;
 114         }
 115
 116         int operator % (int r) {
 117                 int n = 0;
 118                 for (int i = length - 1; i >= 0; i--)
 119                         n = (n * 10 + number[i]) % r;
 120                 return n;
 121         }
 122
 123         int operator %= (int r) {
 124                 return (*this % r);
 125         }
 126
 127         HugeInt operator/ (int r) {
 128                 HugeInt I = 0;
 129                 int n = 0;
 130                 int j = 0;
 131                 for (int i = length - 1; i >= 0 || n >= r; i--) {
 132                         n = (n * 10 + number[i]);
 133                         I.number[j++] = n / r;
 134                         n %= r;
 135                 }
 136
 137                 // reverse string
 138                 for (int i = 0; i < j / 2; i++)
 139                         swap(I.number[i],I.number[j-i-1]);
 140                 I.length = j;
 141                 truncate(I);
 142
 143                 return I;
 144         }
 145
 146         HugeInt operator /= (int r) {
 147                 return (*this / r);
 148         }
 149
 150         // functions
 151         // *veryfied*
 152         void print() {
 153                 for (int i = length - 1; i >= 0; i--)
 154                         putchar(number[i] + '0');
 155         }
 156
 157         void truncate(HugeInt& n) {
 158                 for (int i = n.length - 1; i >= 0 && n.number[i] == 0; i--)
 159                         n.length--;
 160                 if (n.length == 0) {
 161                         n.number[0] = 0;
 162                         n.length = 1;
 163                 }
 164         }
 165
 166         HugeInt power(int p) {
 167                 HugeInt theNew = 1;
 168                 for (int i = 0; i < p; i++)
 169                         theNew *= *this;
 170                 return theNew;
 171         }
 172
 173         bool operator<(const HugeInt& rhs) {
 174                 if (this->length != rhs.length)
 175                         return this->length < rhs.length;
 176                 for (int i = 0; i < this->length; i++)
 177                         if (this->number[i] != rhs.number[i])
 178                                 return this->number[i] < rhs.number[i];
 179                 return false;
 180         }
 181
 182         bool isnull() {
 183                 if (length == 1 && number[0] == 0) {
 184                         return true;
 185                 }
 186                 return false;
 187         }
 188
 189 };
 190
 191
 192 HugeInt dp[2][10000];
 193                 /*
 194                   dp[i][j] = cantidad de maneras diferentes
 195                   en que puedo distribuir las primeras i
 196                   letras de la subsecuencia (b) terminando
 197                   en la letra j de la secuencia original (a)
 198                 */
 199
 200 int main(){
 201   int Casos;
 202   cin >> Casos;
 203   string a, b;
 204   getline(cin, a);
 205   while (Casos--){
 206     getline(cin, a);
 207     getline(cin, b);
 208
 209     if (b.size() > a.size()){
 210       cout << "0" << endl;
 211       continue;
 212     }
 213
 214     int A = a.size(), B = b.size();
 215     dp[0][0] = int(a[0] == b[0]);
 216     for (int j=1; j<A; ++j){
 217       dp[0][j] = dp[0][j-1] + int(a[j] == b[0]);
 218     }
 219
 220     for (int i=1; i<B; ++i){
 221       dp[i%2][0] = 0;
 222       for (int j=1; j<A; ++j){
 223         dp[i%2][j] = dp[i%2][j-1];
 224         if (a[j] == b[i]){
 225           dp[i%2][j] += dp[(i+1)%2][j-1];
 226         }
 227       }
 228     }
 229     dp[(B-1)%2][A-1].print();
 230     putchar('\n');
 231
 232   }
 233   return 0;
 234 }